package leecode

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head.Next == nil {
		return head
	}
	// 创建哑节点作为链表头部
	dummyHead := &ListNode{Next: head}
	pre := dummyHead

	// 找到 left 前一个节点和 right 节点
	for i := 1; i < left; i++ {
		pre = pre.Next
	}
	leftNode := pre.Next
	rightNode := leftNode

	// 反转链表部分
	var next *ListNode
	for i := 0; i < right-left; i++ {
		next = rightNode.Next
		rightNode.Next = next.Next
		next.Next = pre.Next
		pre.Next = next
	}

	// 返回整个链表的头部
	return dummyHead.Next
}
